package features.advance.leetcode.linkedlist.easy;

import features.advance.leetcode.geometry.doublepointer.easy.ListNode;
import features.advance.leetcode.util.TreeUtil;

/**
 *  剑指 Offer 22. 链表中倒数第k个节点
 *
 *  难度：简单
 *
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 *
 * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
 *
 *
 *
 * 示例：
 *
 * 给定一个链表: 1->2->3->4->5, 和 k = 2.
 *
 * 返回链表 4->5.
 *
 * @author LIN
 * @date 2021-06-16
 */
public class Offer22 {
    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        String str = "[1,2,3,4,5]";
        ListNode head = TreeUtil.parseLinkedList(str);
        int k = 2;
        ListNode kthFromEnd = solution.getKthFromEnd(head, k);
        System.out.println(kthFromEnd);
    }
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    static class Solution {
        public ListNode getKthFromEnd(ListNode head, int k) {
            if(head == null || k == 0){
                //考虑特殊情况1、3
                return null;
            }
            ListNode former = head;
            ListNode last = head;
            for(int i = 0;;i++) {
                if(former == null && i<k){
                    //考虑特殊情况2
                    return null;
                }else if(former == null){
                    return last;
                }else if(i>=k){
//                    System.out.println(last.val);
                    last = last.next;
                }
//                System.out.println(former.val);
                former = former.next;
            }
        }
    }

}
